package a.codetop.笔试框架.DP;

public class 最长xx {

    //————————————————————————————————————————————————————————————————————————————————————————————

    /*
      最长公共子序列
      dp[i][j] (不一定含i,j 即中间任意区间交集公共) 0~i和0~j的最长公共子序列长度
    */
    public static int 最长公共子序列(String s1, String s2){
        int n1=s1.length(),n2=s2.length();
        int[][] dp = new int[n1+1][n2+1];
        //
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                //简化代码:我们的索引从1开始省去0边界处理，所以比较这里要比往前一个索引哦
                if(s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        //
        return dp[n1][n2];
    }

    /*
        最长公共子串
        dp[i][j]代表了nums1[0~i-1]中必须含数字nums1[i-1]为结尾和nums2[0~j-1]中必须含数字nums2[j-1]为结尾的的最长子串长度。
    */
    public int 最长公共子串(String s1, String s2){
        int n1=s1.length(),n2=s2.length();
        int[][] dp = new int[n1+1][n2+1];
        //
        int max=0;//因为子串涉及到自成一派重新计数，所以要全遍历一次取max
        //
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=0;
                //
                max=Math.max(dp[i][j],max);
            }
        }
        //
        return max;
    }

    //————————————————————————————————————————————————————————————————————————————————————————————

    /*
        最长递增子序列
        dp[i]含义为：包含i的最长递增子序列长度
     */
    public int 最长递增子序列(int[] nums){
        int n=nums.length;
        int[] dp = new int[n+1];
        //
        for(int i=0;i<dp.length;i++)dp[i]=1;
        //
        int max=1;//dp[i]一定是包含i位置的数的，但最长序列不一定包含结尾的数，所以最终答案不是dp[nums.size()-1]，而是需要for全部遍历找max。
        //
        for(int i=1;i<=n;i++){
            for(int j=i-1;j>=1;j--){
                //初始化的n+1,证明你定义dp数组时定义的时比较前一个（即索引从1开始）
                if(nums[i-1]>nums[j-1]) dp[i]=Math.max(dp[i],dp[j]+1);
                max=Math.max(dp[i],max);
            }
        }
        //
        return max;
    }

    /*
        最长递增子串
     */
    public int 最长递增子串(int[] nums){
        int n=nums.length;
        int count=1;
        int max=1;
        //
        for(int i=1;i<n;i++){
            if(nums[i]>nums[i-1]){//不用old，直接比前一个（连体婴儿）
                count++;
                max=Math.max(count,max);

            }
            else{
                count=1;
            }
        }
        return max;
    }

    //————————————————————————————————————————————————————————————————————————————————————————————

    /*
        最长回文子系列
             极其特殊的定义：dp[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少。
             res也很特殊: dp[0][n]
    */
    public int 最长回文子序列(String s){
        int n=s.length();
        //
        //***关键***：虽然这里加1了[仅仅为了防止边界越界]，但是里面索引还是从0~n-1,即比较si而不是si-1，而且res为n-1
        int[][] dp = new int[n+1][n+1];
        //
        for(int i=0;i<=n;i++)dp[i][i]=1;
        //
        for(int i=n-1;i>=0;i--){
            for(int j=i+1;j<=n-1;j++){
                if(s.charAt(i)==s.charAt(j))dp[i][j]=dp[i+1][j-1]+2;
                else dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
            }
        }
        //
        return dp[0][n-1];
    }

    /*
        最长回文子串：拷贝2份str，一正一反转，求最长公共子串
        中心扩散法也是最优解
    */
    public String 最长回文子串_具体串str(String s){
        String s1=s, s2=new StringBuilder(s).reverse().toString();
        int[][] dp = new int[s1.length()][s2.length()];
        //
        for (int i = 0; i < s1.length(); i++) dp[i][0]= s1.charAt(i)==s2.charAt(0)?1:0;
        for (int j = 0; j < s2.length(); j++) dp[0][j]= s1.charAt(0)==s2.charAt(j)?1:0;
        //
        int maxLen = 0;
        String maxStr = s.charAt(0)+""; //公共子串至少是一个字符（”a、ac“要用）
        //
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if(s1.charAt(i)!=s2.charAt(j)) dp[i][j]=0;
                else{
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>maxLen) {
                        //比公共子串新增————————————————————————————————————
                        int j_fanzhuanqian_index = s2.length()-1-j;
                        int should_i = j_fanzhuanqian_index + dp[i][j]-1;
                        if(should_i==i) {//当前i和should_i比一下
                        //————————————————————————————————————————————————
                            maxLen = dp[i][j];
                            maxStr = s1.substring(i+1-dp[i][j], i+1);
                        }
                    }
                }
            }
        }
        //
        return maxStr;
    }

    //————————————————————————————————————————————————————————————————————————————————————————————

    /*
        最大子串和
     */
    public int 最大子串和(int[] nums){
        int n=nums.length;
        int[] dp=new int[n+1];//从索引1开始,注意索引迁移:dpi、numsi-1
        //
        int max=nums[0];//如果nums可能有负数，不能初始化为0
        //
        for(int i=1;i<=n;i++){
            //有增益
            if(dp[i-1]+nums[i-1]>nums[i-1])dp[i]=dp[i-1]+nums[i-1];
            else dp[i]=nums[i-1];
            max=Math.max(dp[i],max);
        }
        //
        return max;
    }

    //————————————————————————————————————————————————————————————————————————————————————————————




}
